In this note, we examine several nonclosure properties of the classes of sets (of two-dimensional tapes) accepted by nondeterministic two-dimensional on-line tessellation acceptors, nondeterministic one way parallel sequential array acceptors and deterministic one way parallel sequential array acceptors.

One-way sensing simple multihead finite automata with bounds on the number of times of use of sensing function in accepting computations are studied. It is shown that the languages accepted by one-way sensing simple multihead finite automata with constant sensing function bound satisfy the semilinear property, and that for one-way sensing simple multihead finite automata, m+1 times of the use of sensing function are better than m.

This paper investigates the accepting powers of deterministic, Las Vegas, self-verifying nondeterministic, and nondeterministic one-way multi-counter automata with time-bounds. We show that (1) for each k1, there is a language accepted by a Las Vegas one-way k-counter automaton operating in real time, but not accepted by any deterministic one-way k-counter automaton operating in linear time, (2) there is a language accepted by a self-verifying nondeterministic one-way 2-counter automaton operating in real time, but not accepted by any Las Vegas one-way multi-counter automaton operating in polynomial time, (3) there is a language accepted by a self-verifying nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any deterministic one-way multi-counter automaton operating in polynomial time, and (4) there is a language accepted by a nondeterministic one-way 1-counter automaton operating in real time, but not accepted by any self-verifying nondeterministic one-way multi-counter automaton operating in polynomial time.

This paper investigates the accepting powers of one-way alternating and deterministic multi-counter automata operating in realtime. We partially solve the open problem posed in [4], and show that for each k1, there is a language accepted by a realtime one-way deterministic (k+3)-counter automaton, but not accepted by any realtime one-way alternating k-counter automaton.

Let SeH{0}(k) [NSeH{0}(k)] denote the class of languages over a one-letter alphabet accepted by two-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that (i) SeH{0}(2)SeH{0}(3), and (ii) NSeH{0}(2) NSeH{0}(3). This gives an affirmative answer to an open problem in Ref. [3].

This paper investigates the accepting powers of one-way alternatiog finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between counter" and stack-counter" is that the latter can be entered without the contents being changed, but the former cannot.) For each k0 and l0 ((k, l)(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS(k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k0 and l0 ((k, l)(0, 0)), 1UFACS(k, l, real) 1NFACS(k, l, real) 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, foe example, that for each k0 and l0 ((k, l)(0, 0)), and each X{U, N}, 1XFACS(k1, l, real)1AFACS(k, l, real)φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k0, l0 and m1, and each X{U, N}, 1XFACS(k, lm, real)1AFACS(k2m1, l, real)φ.

This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.

This paper introduces a space bounded alternating one-way multihead Turing machine with only universal states, and investigates fundamental properties of this machine. We show for example that for any function L such that [L(n)/n]0, (1) there is a set in [U2-HTM(0)], but not in [Nk-HTM(L(n))], and there is a set in [N2-HTM(0)], but not in [Uk-HTM(L(n))], (2) for each k1, [Uk-HTM(L(n))][U(k+1)-HTM(L(n))], and (3) [Uk-HTM(L(n))][Nk-HTM(L(n))][Dk-HTM(L(n))], where [Uk-HTM(L(n))] denotes the class of sets accepted by L(n) space bounded alternating one-way k-head Turing machines with only universal states, and [Nk-HTM(L(n))]([Dk-HTM(L(n))] denotes the class of sets accepted by L(n) space bounded nondeterministic (deterministic) one-way k-head Turing machines.

In our previous paper, we had proved that the non-closure properties of the class of sets accepted by three-way two-dimensional alternating finite automata (L[TR2-AFA]) under several operations, i.e., row catenation, row closure, row cyclic closure, and projection operations. This letter investigates the remaining closure properties of L[TR2-AFA], especially under column-directional operations, showing that this class L[TR2-AFA] is not closed under column catenation, column closure, or column cyclic closure operations, too. Thus, we have settled the almost closure properties of L[TR2-AFA].

Given a binary picture represented by a region quadtree, it is desirable to identify the amount of (rightward and downward) shifts of the foreground components such that it gives the minimum number of nodes of its quadtree. This problem is called "quadtree normalization. " For this problem, it is unknown whether there exists a linear time algorithm with respect to the size of given images (i. e. , the number of pixels). In this study, we investigate the "one-dimensional version" of the quadtree normalization problem, i. e. , given a binary string represented by a regional binary tree, the task is to identify the amount of (rightward) shift of the foreground components such that it gives the minimum number of nodes of its binary tree. We show that there exists a linear time algorithm for this version.

This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .

This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that limn [d (n)log n/n1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.

This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.

It was unknown whether there exists a language accepted by a two-way nondeterministic one counter automaton, but not accepted by any nondeterministic rebound automaton. This paper solves this problem, and shows that there exists such a language.

Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.

This paper is concerned with a comparative study of the accepting powers of deterministic, Las Vegas, self-verifying nondeterminisic, and nondeterministic (simple) multihead finite automata. We show that (1) for each k 2, one-way deterministic k-head (resp., simple k-head) finite automata are less powerful than one-way Las Vegas k-head (resp., simple k-head) finite automata, (2) there is a language accepted by a one-way self-verifying nondeterministic simple 2-head finite automaton, but not accepted by any one-way deterministic simple multihead finite automaton, (3) there is a language accepted by a one-way nondeterministic 2-head (resp., simple 2-head) finite automaton, but not accepted by any one-way self-verifying nondeterministic multihead (resp., simple multihead) finite automaton, (4) for each k 1, two-way Las Vegas k-head (resp., simple k-head) finite automata have the same accepting powers as two-way self-verifying nondeterministic k-head (resp., simple k-head) finite automata, and (5) two-way Las Vegas simple 2-head finite automata are more powerful than two-way deterministic simple 2-head finite automata.

This paper investigates a relationship between inkdot and one-pebble for two-dimensional finite automata (2-fa's). Especially we show that (1) alternating inkdot 2-fa's are more powerful than nondeterministic one-pebble 2-fa's, and (2) there is a set accepted by an alternating inkdot 2-fa, but not accepted by any alternating one-pebble 2-fa with only universal states.

Let [AONTM(L(n))] ([AOFFTM(L(n))]) be the class of sets accepted by L(n) space bounded alternating on-line (off-line) Turing machines. This paper first gives another proof of the fact that [AONTM(L(n))][AOFFTM(L(n))] for any L(n) such that L(n) log log n and limnL(n)/log n=0. We then show that there exists an infinite hierarchy among [AONTM(L(n))]'s and L[AOFFTM(L(n))]'s with log log nL(n)log n. Finally, we show that [AONTM(L(n))] is not closed under concatenation, Kleene closure, and length preserving homomorphism for any L(n)log log n and limnL(n)/log n=0.

The hierarchies of multihead finite automata over a one-letter alphabet are investigated. Let SeH(k) [NSeH(k) ] denote the class of languages over a one-letter alphabet accepted by deterministic [nondeterministic] sensing two-way k-head finite automata. Let H (k)s[NH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way deterministic [nondeterministic] k-head finite automata. Let SeH(k)s[NSeH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that SeH(k) SeH(k1) and NSeH(k) NSeH(k1) hold for all k3. It is also shown that H(k)s[NH(k)s] H(k1)s[NH (k1)s] and SeH (k)s[NSeH(k)s] SeH(k1)s[NSeH(k1)s] hold for all k1.

For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.